/**
 * Parent Id Based Units/Tree-Structred Data Utilities
 * Parent Id Based Unit must have:
 * 1. id
 * 2. parent_id
 * 3. order
 * Tree-Structred Data Unit must have:
 * 1. id
 * 2. parent_id
 * 3. order
 * 4. c
 */
function PIDTreeUtils() {
};

/**
 * Update a tree structure if nodes' "parent_id" or "order" changed
 */
PIDTreeUtils.update = function(node) {
  var array = [];
  PIDTreeUtils.breakdown(node, array);

  array.sort(function(a, b) {
    return a.order - b.order;
  });
  PIDTreeUtils.assemble(node, array);
};

/**
 * Break node to array
 */
PIDTreeUtils.breakdown = function(node, array) {
  for ( var i = 0, il = node.c.length; i < il; i++) {
    var tmp = node.c[i];
    PIDTreeUtils.breakdown(tmp, array);
  }
  delete node.c;
  array.push(node);
};

/**
 * Assemble array to node
 */
PIDTreeUtils.assemble = function(node, array) {
  node.c = [];
  var i = 0;
  while (i < array.length) {
    if (array[i].parent_id == node.id) {
      node.c.push(array[i]);
      array.splice(i, 1);
    } else {
      i++;
    }
  }
  for ( var i = 0, il = node.c.length; i < il; i++) {
    PIDTreeUtils.assemble(node.c[i], array);
  }
};

/**
 * Check if the "successor" is a successor the "ancestor"
 */
PIDTreeUtils.isSuccessor = function(ancestor, successor) {
  for ( var i = 0, il = ancestor.c.length; i < il; i++) {
    var tmp = ancestor.c[i];
    if (tmp.id == successor.id) {
      return true;
    }
    if (PIDTreeUtils.isSuccessor(tmp, successor)) {
      return true;
    }
  }
  return false;
};

/**
 * Return the needle's "Joint Siblings" and "Ancestors" in the haystack
 * { found: true/false
 *   youngerBro: node below needle
 *   olderBro: node up neeld
 *   ancesters: parent node, grand parent node, ...
 * }
 */
PIDTreeUtils.getFamily = function(haystack, needle) {
  return PIDTreeUtils._goFamily(haystack, needle, [])
};

/**
 * INTERNAL FUNCTION
 */
PIDTreeUtils._goFamily = function(haystack, needle, ancestors) {
  for ( var i = 0, il = haystack.c.length; i < il; i++) {
    var tmp = haystack.c[i];
    if (tmp.id == needle.id) {
      var olderBro = (i > 0) ? haystack.c[i - 1] : null;
      var youngerBro = (i < il - 1) ? haystack.c[i + 1] : null;
      return {
        found : true,
        olderBro : olderBro,
        youngerBro : youngerBro,
        ancestors : ancestors
      };
    }
    ancestors.push(tmp);
    var family = PIDTreeUtils._goFamily(tmp, needle, ancestors);
    if (family.found) {
      return family;
    }
    ancestors.pop();
  }
  return {
    found : false,
    olderBro : null,
    youngerBro : null,
    ancestors : ancestors
  };
};

/**
 * Find a node by id
 */
PIDTreeUtils.findById = function(haystack, needle) {
  if (haystack.id == needle) {
    return haystack;
  }
  for ( var i = 0, il = haystack.c.length; i < il; i++) {
    var result = PIDTreeUtils.findById(haystack.c[i], needle);
    if (result) {
      return result;
    }
  }
  return null;
};

/**
 * Last Child
 */
PIDTreeUtils.isLastChild = function(haystack, needle) {
  if (haystack.c.length > 0 && haystack.c[haystack.c.length - 1].c.length == 0 && haystack.c[haystack.c.length - 1].id == needle) {
    return true;
  }
  if (haystack.c.length > 0) {
    return PIDTreeUtils.isLastChild(haystack.c[haystack.c.length - 1], needle);
  }
  return false;
};

/**
 * Remove a node by id
 */
PIDTreeUtils.removeById = function(haystack, needle) {
  for ( var i = 0, il = haystack.c.length; i < il; i++) {
    if (haystack.c[i].id == needle) {
      haystack.c.splice(i, 1);
      return true;
    }
    if (PIDTreeUtils.removeById(haystack.c[i], needle)) {
      return true;
    }
  }
  return false;
};
